package com.xyhuo.leetcode;

public class MaximumTripletValue {

    public long maximumTripletValueOld(int[] nums) {
        int len = nums.length;
        long ans = 0l;
        for (int i = 0; i < len - 2; i++) {
            for (int j = i + 1; j < len; j++) {
                int tmp = nums[i] - nums[j];
                if (tmp == 0) {
                    continue;
                }
                int plusNum = 0;
                for (int k = j + 1; k < len; k++) {
                    if (tmp < 0 && nums[k] < plusNum) {
                        plusNum = nums[k];
                    } else if (tmp > 0 && nums[k] > plusNum) {
                        plusNum = nums[k];
                    }
                }
                long tmpAns = 1l * tmp * plusNum;
                if (tmpAns > ans) {
                    ans = tmpAns;
                }
            }
        }
        return ans;
    }

    public long maximumTripletValue(int[] nums) {
        int len = nums.length;
        int[][] m = new int[len][2];
        if (nums[0] > nums[1]) {
            m[1][0] = nums[0];
            m[1][1] = nums[1];
        } else {
            m[1][0] = nums[1];
        }
        for (int i = 2; i < len; i++) {
            if (nums[i] == nums[i - 1] || nums[i] == m[i - 1][0]) {
                m[i][0] = m[i - 1][0];
                m[i][1] = m[i - 1][1];
                continue;
            }
            if (nums[i] > m[i - 1][0]) {
                m[i][0] = nums[i];
            } else if (nums[i] < m[i - 1][0]) {
                m[i][0] = m[i - 1][0];
                if (0 == m[i - 1][1] || nums[i] < m[i - 1][1]) {
                    m[i][1] = nums[i];
                } else {
                    m[i][1] = m[i - 1][1];
                }
            }
        }

        long ans = 0l;
        int[] max = new int[len];
        for (int i = 1; i < len; i++) {
            if (m[i][1] == 0) {
                max[i] = max[i - 1];
                continue;
            }
            int tmpMax = m[i][0] - m[i][1];
            if (tmpMax > max[i - 1]) {
                max[i] = tmpMax;
            } else {
                max[i] = max[i - 1];
            }
            long tmpAns = 1l * nums[i] * max[i - 1];
            if (tmpAns > ans) {
                ans = tmpAns;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
//        int[] nums = {6, 11, 12, 12, 7, 9, 2, 11, 12, 4, 19, 14, 16, 8, 16};
//        int[] nums = {12, 6, 1, 2, 7};
        int[] nums = {15, 12, 2, 14, 15, 18, 15, 20, 14, 5, 14, 14, 11, 13, 7};
        MaximumTripletValue m = new MaximumTripletValue();
        long l = m.maximumTripletValue(nums);
        System.out.println(l);
    }
}
